package ua.mykola.ds.tree.traversal;

import java.util.List;

import ua.mykola.ds.tree.Node;

public class PreorderInorderRecreateTree {

	public Node recreate(List<Object> preOrder, List<Object> inOrderList) {

		if (preOrder.size() == 0 || inOrderList.size() == 0) {
			return null;
		}

		Object value = preOrder.get(0);
		Node node = new Node(value);

		int inorderPos = inOrderList.indexOf(value);
		List<Object> leftInorder = inOrderList.subList(0, inorderPos);
		List<Object> rightInorder = inOrderList.subList(inorderPos + 1, inOrderList.size());

		List<Object> leftPreOrder = preOrder.subList(1, inorderPos + 1);
		List<Object> rightPreOrder = preOrder.subList(inorderPos + 1, preOrder.size());

		node.left = recreate(leftPreOrder, leftInorder);
		node.right = recreate(rightPreOrder, rightInorder);

		return node;
	}
}
